package splay;

public class ClassR implements SplayTree {

	private NoSplay root;

	public ClassR() {
		this.root = new NoSplay();
	}

	private NoSplay rightRotate(NoSplay no) {
		NoSplay pivot = new NoSplay();

		pivot.setLeft(no.getLeft().getRight());
		pivot.setRight(no.getRight());
		pivot.setKey(no.getKey());

		no.setKey(no.getLeft().getKey());
		no.setLeft(no.getLeft().getLeft());
		no.setRight(pivot);

		return no;
		
/*		NoSplay parent = no.getParent();
		NoSplay aux = no.getRight();
		
		no.setParent(null);	// muda o pai de filho
		
		no.setRight(parent); // muda o filho Direito de filho

		parent.setParent(no); // muda o pai de pai
		
		parent.setLeft(aux); // muda o filho left de pai
		
		if (aux != null) // muda o pai do auxiliar
			aux.setParent(parent);
		
		root = no;
		
		return root;*/
		
	}

	private NoSplay leftRotate(NoSplay no) {
		NoSplay pivot = new NoSplay();

		pivot.setRight(no.getRight().getLeft());
		pivot.setLeft(no.getLeft());
		pivot.setKey(no.getKey());

		no.setKey(no.getRight().getKey());
		no.setRight(no.getRight().getRight());
		no.setLeft(pivot);

		return no;
	}

	private void splay(NoSplay no) {
		NoSplay avo = no.getParent().getParent();
		NoSplay pai = no.getParent();
		
		if (this.root.getKey() == pai.getKey()) { // Primeiro Caso
			if (this.root.getLeft().getKey() == no.getKey()) {
				rightRotate(pai); // Zig
			} else {
				leftRotate(pai); // Zig
			}
		} 
		
		
		
		else if ((avo.getLeft().getKey() == pai.getKey())
				&& (pai.getLeft().getKey() == no.getKey())) { // Segundo Caso
			rightRotate(avo); // Zig_Zig
			rightRotate(pai);
		} 
		
		else if ((avo.getRight().getKey() == pai.getKey())
				&& (pai.getRight().getKey() == no.getKey())) {
			leftRotate(avo); // Zig_Zig
			leftRotate(pai);
		} 
		
		
		
		else { // Terceiro Caso
			if ((avo.getLeft().getKey() == pai.getKey())
					&& (pai.getRight().getKey() == no.getKey())) {
				leftRotate(pai); // Zig_Zag
				rightRotate(avo);
			} else if ((avo.getRight().getKey() == pai.getKey())
					&& (pai.getLeft().getKey() == no.getKey())) {
				rightRotate(pai); // Zig_Zag
				leftRotate(avo);
			}
		}
	}

	@Override
	public int height() {
		int respostaAlturaEsquerda = -1;
		int respostaAlturaDireita = -1;
		
		NoSplay temporario = this.root;
		while (!temporario.isEmpty() && !temporario.isLeaf()) {
			if (!temporario.getLeft().isLeaf()) {
				temporario = temporario.getLeft();
				respostaAlturaEsquerda++;
			} else if (!temporario.getRight().isEmpty()) {
				temporario = temporario.getRight();
				respostaAlturaEsquerda++;
			} else if (!temporario.getLeft().isEmpty()) {
				temporario = temporario.getRight();
				respostaAlturaEsquerda++;
			} else {
				break;
			}
		}
		
		temporario = this.root;
		while (!temporario.isEmpty()) {
			if (!temporario.getRight().isLeaf()) {
				temporario = temporario.getRight();
				respostaAlturaDireita++;
			} else if (!temporario.getLeft().isEmpty()) {
				temporario = temporario.getLeft();
				respostaAlturaDireita++;
			} else if (!temporario.getRight().isEmpty()) {
				temporario = temporario.getRight();
				respostaAlturaDireita++;
			} else {
				break;
			}
		}
		return Math.max(respostaAlturaEsquerda, respostaAlturaDireita);
	}

	public NoSplay search(int key) {

		NoSplay ptr = root;
		while (true) {
			if (ptr == null || ptr.isEmpty()) {
				return ptr;
			}
			if (key == ptr.getKey()) {
				break;
			} else if (ptr.getKey() > key) {
				ptr = ptr.getLeft();
			} else if (ptr.getKey() < key) {
				ptr = ptr.getRight();
			}
		}
		return ptr;
	}

	public void insert(int key) {

		NoSplay auxiliar = root;

		while (!auxiliar.isEmpty()) {
			if (auxiliar.getKey() != key) {
				if (auxiliar.getKey() < key) {
					auxiliar = auxiliar.getRight();
				} else if (auxiliar.getKey() > key) {
					auxiliar = auxiliar.getLeft();
				}
			}
		}

		auxiliar.setKey(key);
		auxiliar.setLeft(new NoSplay());
		auxiliar.setRight(new NoSplay());

		// splay(root);

	}

	public void delete(int key) {
		NoSplay ptr = root;
		while (true) {
			if (ptr == null || ptr.isEmpty()) {
				return;
			}
			if (key == ptr.getKey()) {
				if (ptr.isLeaf()) {

					ptr.setKey(-1);
					ptr.setParent(new NoSplay());
				}

				else {
					ptr.setKey(-1);
					root = ptr.getLeft();
					root = ptr.getRight();

				}
				break;
			} else if (ptr.getKey() > key) {
				ptr = ptr.getLeft();
			} else if (ptr.getKey() < key) {
				ptr = ptr.getRight();
			}
		}
	}

	@Override
	public String preOrder() {
		return stringPre(root);
	}

	private String stringPre(NoSplay no) {
		StringBuilder resp = new StringBuilder();
		if (!no.isEmpty()) {
			resp.append(stringPre(no.getLeft()));
			resp.append(stringPre(no.getRight()));
			resp.append(no.getKey() + " ");
		}
		return resp.toString();
	}

	@Override
	public int size() {
		if (root.isEmpty()) {
			return 0;
		}

		String resp = preOrder();

		String[] resp2 = resp.split(" ");

		return resp2.length;
	}

}
